개발자 면접질문과 답변들. 더 많은 내용은 깃허브 저장소에서 확인할 수 있습니다 (https://github.com/jeonyeohun/GetReadyForInterview)

배열 & 링크드 리스트

베열과 링크드 리스트의 차이가 뭐에요?

• 배열은 연속된 메모리 공간에 데이터를 저장하고 리스트는 비연속적인 공간에 데이터를 저장한 뒤 두 데이터를 노드로 연결한다는 차이점이 있습니다.

그럼 배열이랑 링크드 리스트의 탐색시간을 말해볼래요?

• 배열은 인덱스를 통해 데이터에 접근이 가능합니다. 따라서 시간복잡도는 O(1) 입니다. 반면에 리스트는 처음부터 연결된 노드들을 따라가며 데이터를 찾아야하기 때문에 최악의 경우에는 첫 노드에서 탐색을 시작하고 탐색할 노드가 마지막에 있는 경우가 됩니다. 따라서 시간복잡도 O(N) 입니다.

링크드 리스트에서 삭제 연산을 하는 과정을 설명해보세요

• 삭제 연산을 하기 위해서는 먼저 가장 첫 노드부터 바로 다음노드가 삭제하고자 하는 노드일때까지 탐색을 진행합니다. 삭제할 노드의 이전 노드를 만나면 해당 노드의 다음노드 포인터를 삭제할 노드의 다음 노드로 만들어줍니다. 이렇게 하면 삭제할 노드로 가는 유일한 연결이 끊어지고 해당 노드는 리스트에서 제외됩니다.

그럼 어떤 경우에 링크드 리스트를 쓰는게 더 적절할까요?

• 배열은 삽입과 삭제연산이 O(N) 인 반면에 링크드 리스트는 O(1) 의 시간복잡도를 가집니다. 따라서 삽입과 삭제가 빈번한 상황이라면 링크드 리스트를 사용하는게 더 유리합니다.

스택 & 큐

스택과 큐의 차이점을 설명해보세요

• 스택은 LIFO 성격을 띄는 자료구조로 가장 마지막에 넣은 원소를 가장 먼저 꺼냅니다. 반면에 큐는 FIFO 성격의 자료구조로 먼저 들어간 원소를 가장 먼저 꺼냅니다.

배열과 링크드 리스트 중 하나로 스택을 구현한다면 어떤 걸 선택할래요?

• 스택은 마지막 원소만 삭제해주면 됩니다. 만약 단방향 링크드 리스트를 사용한다면 마지막 바로 이전 노드까지 탐색을 진행한 뒤에 연결을 끊어줘야 합니다. 따라서 O(N)의 시간복잡도가 요구됩니다. 배열을 사용하면 배열의 길이만 1 줄여주면 되기 떄문에 O(1)의 시간복잡도가 요구됩니다. 따라서 배열을 사용하는 것이 더 효율적입니다.

원형 큐는 시작과 끝 인덱스 관리를 어떻게 하는지 설명해보세요.

• 원형 큐는 front 와 rear 를 가르키는 포인터를 사용합니다. 삽입할 때는 항상 rear 포인터의 위치에 값을 넣고 삭제할때는 front 가 가르키는 위치의 다음 값을 삭제합니다. 두 포인터 모두 같은 인덱스에서 시작하고 rear 는 삽입이 될떄마다 한칸 씩 이동, front 는 삭제가 될때마다 한칸씩 이동합니다. 이 때문에 front 는 항상 비어있는 인덱스를 가르킵니다. 만약 rear의 인덱스가 front 의 인덱스와 같다면 원형 큐가 가득 찬 것으로 판단합니다.

그럼 front 인덱스의 값은 왜 비워두나요?

• 원형큐는 rear + 1 을 큐의 전체 크기로 모듈로 연산한 값을 front 값과 비교합니다. 이 연산은 큐가 공백상태인지, 포화상태인지 구분하기 위한 용도로 사용됩니다. 따라서 rear 가 front 의 바로 이전 인덱스에 있을 경우 rear == front 가 만족되기 때문에 front 에는 값이 채워질 수 없습니다.

스택으로 큐를 만드는 방법을 말해보세요.

• 스택 두 개를 사용하면 큐를 구현할 수 있습니다. 한 개의 큐는 데이터를 쌓는 용도로 사용하고 다른 하나는 데이터를 삭제하는 용도로 사용합니다. push 연산이 들어올 때는 첫번째 큐에 데이터를 모두 넣습니다. 그리고 pop 연산이 수행되면 첫번째 스택에서 데이터를 순서대로 pop 해 모두 다른 한 쪽의 스택으로 넣어주고 마지막으로 들어간 데이터를 다시 pop 해주면 가장 첫번째로 넣은 데이터를 꺼낼 수 있습니다.

우선순위 큐에 대해서 설명해보세요.

• 우선순위 큐는 힙 자료구조를 사용해서 원소들간의 우선순위에 따라 가장 우선순위가 높은 원소를 꺼내는 자료구조입니다. 새로운 데이터를 삽입하거나 삭제할 때마다 힙의 완전이진트리를 재배열해주어야 하기 때문에 삽입과 삭제에 O(logN)의 시간복잡도가 요구됩니다.

힙 말고 다른 방법으로는 우선순위 큐를 만들 수 없을까요?

• 링크드 리스트로도 우선순위 큐를 만들 수 있습니다. 이때 삽입은 O(N), 삭제는 O(1) 의 시간복잡도를 가집니다. 즉, 데이터의 개수가 많아질 수록 효율이 떨어집니다.

그래프

그래프의 정의가 뭐에요?

• 그래프는 정점과 간선으로 정점 간의 관계를 표현하는 자료구조입니다.

그럼 트리랑 그래프는 무슨 차이가 있어요?

• 트리는 그래프의 한 종류이며 몇가지 조건을 가집니다. 트리는 항상 간선의 개수가 정점의 개수보다 하나 더 적고, 사이클이 발생하지 않습니다. 그리고 모든 정점들이 연결되어 있습니다.

Dense 그래프와 Sparse 그래프에 대해서 설명해보세요.

• Dense 그래프는 정점의 개수보다 간선의 개수가 더 많은 그래프를 의미하고 Sparse 그래프는 간선의 개수보다 정점의 개수가 더 많은 그래프를 의미합니다.

해시 테이블

해시테이블이 무엇인지 설명해보세요.

• 헤시 테이블은 Key-Value 맵핑으로 데이터를 저장하는 자료구조입니다. 어떤 Key 값에 대해서 해당 키에대한 고유한 인덱스를 해시함수를 통해 만들고 Value에 이 인덱스를 부여합니다. Key 값을 넣으면 바로 Value가 나오기 때문에 O(1) 의 시간복잡도를 가집니다.

해시 충돌에 대해서 설명해보세요.

• 해시 충돌은 어떤 키 값들이 해시 함수를 통해 동일한 해시값을 가지게 되는 현상을 의미합니다.

그럼 해시 충돌을 해결할 수 있는 방법을 말해보세요.

• 두 가지 대표적인 방법이 있습니다. 분리 연결법과 개방 주소법입니다.
• 분리 연결법은 어떤 Key 에 대한 해시함수로 얻은 해시가 이미 존재하여 충돌이 일어났을 때 기존에 있던 데이터 뒤에 새로운 데이터를 연결시켜주는 방법입니다. 데이터에는 Key와 Value 가 모두 저장되고 Key 값을 탐색해서 입력된 Key 와 일치하는 데이터의 Value 를 반환합니다.
• 개방주소법은 어떤 Key 에 대해 해시 충돌이 일어났을 때 다른 비어있는 인덱스를 찾아 데이터를 저장하는 방법입니다. 다른 인덱스를 찾는 방법은 동일한 방법을 적용해서 진행해야합니다.

분리 연결법에는 어떤 단점이 있을까요?

• 해시충돌이 일어날 때마다 같은 인덱스에 새로운 데이터를 계속 연결시키기 때문에 같은 해시에 대한 충돌이 여러번 일어나면 다른 인덱스에 빈 공간이 있는 경우에도 한쪽으로 데이터가 쏠릴 수 있습니다. 또한 데이터 저장을 위해 추가적인 메모리를 사용해야한다는 단점도 있습니다.

힙

힙 자료구조를 배열로 구현할 때 0번 인덱스를 사용하지 않는 이유를 말해보세요.

• 배열로 힙을 구현하면 완전이진트리를 구현하기 위해 부모 자녀노드의 인데스 위치를 부모노드의 인데스 X 2(왼쪽 노드), 부모노드의 인데스 X 2 + 1(오른쪽 노드) 로 구성합니다. 루트노드를 0으로 설정하면 이 연산을 수행할 수 없습니다.

힙에 새로운 노드가 삽입되는 과정과 시간복잡도를 설명해보세요.

• Max Heap 을 기준으로 힙에 새로운 노드를 삽입하기 위해서 완전이진트리의 마지막 노드로 새 노드를 추가합니다. 이 노드를 부모노드와 비교하고 새로 추가한 노드가 더 크다면 부모노드와 자리를 바꿔줍니다. 새로 부모노드가 된 노드는 다시 자신의 부모노드와 비교를 해서 자리를 바꾸고 더 이상 자리를 바꿀 수 없을 때까지 진행합니다. 따라서 최악의 경우에는 완전이진트리의 리프노드에서 루트노드까지 올라가며 교환연산을 수행하기 때문에 O(logN)의 시간복잡도를 가집니다.

힙의 삭제 과정과 시간복잡도를 설명해보세요.

• 힙의 삭제연산은 루트노드를 삭제하는 연산입니다. 이때 완전이진트리의 마지막 노드의 값을 루트노드에 덮어씌워줍니다. 그리고 트리 재조정을 위해 루트노드부터 밑으로 내려오면서 비교&교환 연산을 수행합니다. 따라서 최악의 경우에는 루트노드부터 리프노드까지 비교연산을 수행하기 때문에 O(logN)의 시간복잡도를 가집니다.

트리

트리를 정의해보세요.

• 트리는 사이클이 없고 모든 정점이 간선으로 연결된 자료구조입니다. 사이클이 없어야하기 때문에 간선의 개수는 항상 정점의 개수보다 하나 작습니다.

이진트리를 탐색하는 세 방법에 대해서 설명해보세요.

• 이진트리를 탐색할 때 전위순회, 중위순회, 후위순회 세가지 방법으로 탐색을 할 수 있습니다.
• 전위, 중위, 후위는 부모노드와 자녀노드를 체크하는 순서를 타나냅니다. 전위순회는 부모노드를 먼저 체크하고 자녀노드의 서브트리를 체크합니다. 중위순회는 좌측 자녀노드의 서브트리를 체크하고 더 이상 탐색이 불가능 할 때 부모노드를 체크한 뒤 우측 자녀노드의 서브트리 탐색을 시작합니다. 마지막으로 후위순회는 좌측 서브트리, 우측서브트리를 모두 체크 한 뒤에 부모 노드를 체크합니다.

완전이진트리가 뭔지 설명해보세요.

• 완전이진트리는 최대 두 개의 자녀노드를 가지는 이진트리로 마지막 레벨을 제외한 모든 레벨에 노드가 채워져있고 마지막 레벨은 왼쪽부터 빈 노드 없이 채워져 있어야합니다.

이진탐색트리에 대해서 설명해보세요.

• 이진탐색트리는 트리와 트리 내 모든 서브트리의 루트노드를 기준으로 값이 더 작은 노드는 왼쪽, 값이 더 큰 노드는 오른쪽에 위치하게하는 이진트리입니다.

이진탐색트리의 삭제연산을 설명해보세요.

• 이진탐색트리의 삭제연산은 세 가지 경우로 나뉘어집니다.
• 첫번째 경우는 삭제하려는 노드의 자녀노드가 없는 경우입니다. 이 경우는 삭제하려는 노드를 탐색해서 해당노드를 삭제합니다.
• 두번째 경우는 삭제하려는 노드가 하나의 자녀노드를 가지는 경우입니다. 이 경우는 삭제하려는 노드의 자녀노드를 삭제하려는 노드의 부모노드와 연결시킨 후 노드를 삭제합니다.
• 마지막 경우는 삭제하려는 노드가 두 개의 자녀노드를 가지는 경우입니다. 이 경우는 삭제하려는 노드의 자녀 서브트리에서 왼쪽 서브트리를 사용한다면 최댓값을, 오른쪽 서브트리를 사용한다면 최소값을 삭제하려는 노드의 값으로 대체하고 해당 자녀노드를 삭제합니다.

이진탐색트리의 삽입 연산을 설명해보세요.

• 이진탐색트리는 새로운 노드의 값을 기준으로 더 이상 자녀노드가 없을 때까지 탐색을 진행하다가 해당 노드의 자녀노드로 새로운 노드를 연결시킵니다.

이진탐색트리의 시간복잡도가 어떻게 되는지 알아요?

• 이진탐색트리는 삽입과 삭제 모두 탐색을 사용해야하고 탐새은 각 노드를 대소비교하며 진행하기 때문에 트리의 높이가 h 라고 할 때, O(h)의 시간복잡도가 요구됩니다.

이진탐색트리의 단점은 뭐에요?

• 이진탐색트리는 루트노드를 기준으로 새로운 노드를 삽입하기 때문에 만약 루트노드보다 큰 값을 가진 노드가 계속해서 들어오면 불균형한 트리가 생성됩니다.

AVL 트리에 대해서 설명해보세요.

• AVL 트리는 트리의 불균형을 막기위해 새로운 노드가 트리에 추가될 때마다 좌측 서브트리와 우측 서브트리의 높이의 차를 사용해 트리의 균형을 맞추어줍니다. 만약 불균형이 발견되면 세 루트노드 중 중간 값을 가진 노드를 루트노드로 만들고 이를 기준으로 좌우에 서브트리를 위치시킵니다.

AVL 트리의 시간복잡도는 이진탐색트리와 어떻게 달라요?

• AVL 트리는 이진탐색트리와 달리 트리 재조정을 통해서 트리의 상태를 항상 균형을 유지하기 때문에 O(logN)의 시간복잡도를 가집니다.

Red-Black Tree 가 가지는 특징을 말해보세요

• 레드블랙트리는 세 조건을 만족하는 트리입니다.
• 루트노드와 리프노드는 항상 Black 이어야 합니다.
• Red 노드의 자녀노드는 모두 Black 이어야합니다.
• 루트노드에서 어떤 리프노드까지의 경로에 있는 Black 노드의 수는 모두 동일합니다.

Red-Black Tree 의 삽입과정을 설명해보세요

• 레드블랙트리는 먼저 새로운 노드 값을 기준으로 더 이상 갈 수 있는 자녀노드가 없는 노드까지 이동한 뒤 새로운 노드를 연결시킵니다. 이때 새로운 노드를 레드로 설정합니다. 그리고 레드블랙 규칙에 따라 트리를 재조정해야 하는데 다음 두 가지 경우로 나뉘어집니다.
• 먼저 방금 삽입한 노드의 부모노드와 해당 부모노드와 같은 레벨에 있는 이웃 노드가 모두 레드라면 이 두 노드를 블랙으로 만들고 두 노드의 부모노드, 즉 새로 삽입한 노드의 조상노드를 블랙으로 만들어줍니다.
• 만약 방금 삽입한 노드의 보모노드의 레벨에 있는 이웃 노드가 블랙이라면 방금 삽입한 노드를 중심으로 왼쪽으로 회전시킨 뒤 만들어진 리프노드를 중김으로 다시 오른쪽으로 한 번 회전시킵니다. 그리고 중심이 되었던 두 노드의 색깔을 서로 바꾸어줍니다.